# 1363
from typing import List

from itertools import combinations
class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        s2b = sorted(digits)
        b2s = reversed(s2b)
        s = sum(digits)
        if s % 3 == 0:
            res = ''.join([str(d) for d in b2s])
            if len(res) != 0 and all([r == '0' for r in res]):
                return "0"
            return res
        w = s % 3
        # print(w)
        # Remove 1 number
        nums1 = [d for d in s2b if d % 3 == w]
        if len(nums1) != 0:
            removed = [min(nums1)]
        else:
            # Remove 2 numbers
            for a, b in combinations(s2b, 2):
                if (a + b) % 3 == w:
                    removed = [b ,a]
                    break
        # print(removed)
        i = 0
        res = ''
        if removed:
            for d in b2s:
                if i < len(removed) and d == removed[i]:
                    i += 1
                else:
                    res += str(d)
        if len(res) != 0 and all([r == '0' for r in res]):
            return "0"
        return res

if __name__ == '__main__':
    s = Solution()
    print(s.largestMultipleOfThree([8,1,9]))
    print(s.largestMultipleOfThree([8,6,7,1,0]))
    print(s.largestMultipleOfThree([1]))
    print(s.largestMultipleOfThree([0,0,0,0,0,0]))
    print(s.largestMultipleOfThree([5,8]))
